/**
 * author: MaHX
 * date: 2019/8/19/14:06
 * description:
 **/
public class QuickSort {
    public static int sortOnce(int[] arrs, int begin, int end) {
        int flag = arrs[begin];
        int i = begin;
        int j = end;
        while (i < j) {
            while (i < j) {
                if (arrs[j] < flag) {
                    arrs[i] = arrs[j];
                    break;
                }
                j--;
            }
            while (i < j) {
                if (arrs[i] >= flag) {
                    arrs[j] = arrs[i];
                    break;
                }
                i++;
            }
        }
        arrs[i] = flag;
        return i;

    }

    public static void sort(int[] arrs, int begin, int end) {
        if (begin < end) {
            int index = sortOnce(arrs, begin, end);
            sort(arrs, begin, index - 1);
            sort(arrs, index + 1, end);
        }
    }

    public static void main(String args[]) {
        int[] arrs = new int[]{7, 5, 9, 1, 4, 7, 8, 6};
        sort(arrs, 0, arrs.length - 1);
        for (int i = 0; i < arrs.length; i++) {
            System.out.println(arrs[i]);
        }
    }
}
